package hot100.logos91To100;

/**
 * @author logos
 * date 2025/7/18 19:18
 * @version v1.0
 * @Package hot100.logos91To100
 */
public class logos93 {

    /**
     * 93. 最长回文子串
     * https://leetcode.cn/problems/longest-palindromic-substring/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        public String longestPalindrome(String S) {
            char[] s = S.toCharArray();
            int n = s.length;
            int ansLeft = 0;
            int ansRight = 0;
            for (int i = 0; i < 2 * n - 1; i++) {
                int l = i / 2;
                int r = (i + 1) / 2;
                while (l >= 0 && r < n && s[l] == s[r]) {
                    l--;
                    r++;
                }
                if (l + 1 <= r - 1) {
                    if (r - l - 1 > ansRight - ansLeft) {
                        ansLeft = l + 1;
                        ansRight = r;
                    }
                }
            }

            return S.substring(ansLeft, ansRight);
        }
    }
}
